1. Field of the Invention
The present invention relates to distributed interactive applications, and, more particularly, hierarchical space partitioning for scalable data dissemination in large-scale distributed interactive applications.
2. Description of the Related Art
A distributed interactive application (“DIA”) allows users connected via a network to interact synchronously with a shared application state. Examples of DIAs include, but are not limited to, networked virtual environments and online multiplayer gaming.
The DIA may be supported by a communication infrastructure which manages the distribution of state updates to objects based on the proximity of the objects in a virtual space. The virtual space is a type of application space. An application space is a collection of objects and their associated states. In the context of the present disclosure, the term “object” refers to a set of static or dynamic attributes and a set of methods that can modify those attributes. The sets of methods and attributes are specific to the application (e.g., for a virtual environment application, the objects have graphical and position attributes and methods that describe their object dynamics). The application space can be partitioned and replicated at several clients in a DIA. A virtual space is a type of application space in which objects are associated with a graphical (typically two- or three-dimensional) representation.
Dynamic attributes of the objects in the virtual space are controlled using state updates. In a distributed virtual space, partitions of the virtual space are replicated at each participating client and controlled locally. The state updates are used to synchronize a locally controlled state among all replicas of a partition.
One method of managing the distribution of state updates is through client subscriptions to the set of states which need to be synchronized. This is commonly referred to as the “communication interest” of a client. The communication interest of a client can be specified using a multidimensional intervals (e.g., a client is interested in all updates that have a position attribute in a specified interval). The union of communication interests of participating clients is commonly referred to as the “communication interest space.”
One way to represent the virtual space is by using scene-graphs. However, representation of the virtual space using scene-graphs is not efficient for managing the state of DIAs for at least two reasons. First, although scene-graphs preserve relations between objects (e.g., nodes in a hierarchy of nodes that compose larger structures), scene-graphs do not index the virtual space for efficient spatial queries (e.g., retrieve all objects in the <domain, attributes>). Second, scene-graphs do not provide for dynamic load-balancing of indexed objects.
Alternative representations of the virtual space using spatial data structures (e.g., quad-trees, oct-trees, binary space partitioning) have been proposed, but these structures were designed primarily for rendering (e.g., visibility culling) and physical modeling (e.g., collision checking) operations and do not support the distribution of state updates.